#include <iostream>
#include <algorithm>
#include <vector>
struct Node{
char c=0;
int freq=0;
Node *left=nullptr, *right=nullptr;
Node(){}
Node(int _freq, Node* _left, Node* _right): freq(_freq), left(_left), right(_right){}
void set(char _c, int _freq){
this->c=_c;
this->freq=_freq;
}
};
bool cmp(const Node* n1, const Node* n2){
return n1->freq>n2->freq;
}
struct Series{
Node** nodes;
int sz, cap=0;
Series(int _sz): sz(_sz) {
nodes=new Node*[sz];
}
Series& operator=(Series& other){
this->sz=other.sz;
for(int i=0; i<this->sz; ++i){
this->insert(other[i]->c, other[i]->freq);
}
return *this;
}
void insert(char c, int freq){
Node* nN=new Node;
nN->set(c, freq);
nodes[cap++]=nN;
}
Node* operator[](int index){
return nodes[index];
}
void sort(void){
std::stable_sort(nodes, nodes+sz, cmp);
}
void merge_small(void){
this->sort();
int ind1=sz-2, ind2=sz-1;
int freq=this->nodes[ind1]->freq+this->nodes[ind2]->freq;
Node* nN=new Node(freq, this->nodes[ind2], this->nodes[ind1]);
this->nodes[ind1]=nN;
sz--;
}
Node* root(void){
return nodes[0];
}
};
Node* Huffman(Series C){
int n=C.sz;
Series Q=C;
for(int i=0; i<n-1; ++i){
Q.merge_small();
}
return Q.root();
}
void Print(Node* node, std::vector<int> code){
if(node->left==nullptr && node->right==nullptr){
std::cout<<node->c<<": ";
for(int i=0; i<code.size(); ++i) std::cout<<code[i]<<" ";
std::cout<<std::endl;
return;
}
code.push_back(0);
Print(node->left, code);
code.pop_back();
code.push_back(1);
Print(node->right, code);
code.pop_back();
}
int main(void){
char c[]={'f', 'e', 'c', 'b', 'd', 'a'};
int f[]={5, 9, 12, 13, 16, 45};
int sz=sizeof(f)/sizeof(int);
Series seri(sz);
for(int i=0; i<sz; ++i) seri.insert(c[i], f[i]);
Node* root=Huffman(seri);
std::vector<int> null;
Print(root, null);
return 0;
}